package C.栈;

import java.util.*;

public class  _155_最小栈 {

    /**
     * 自解：用数组实现栈 pop函数存在问题
     */
    class MinStack{
        private int[] stack;
        private int size;

        Map<Integer,Integer> minSet = new HashMap<>();
        int count=0;
        int min = Integer.MAX_VALUE;
        /** initialize your data structure here. */
        public void MinStack() {

            stack = new int[0];
            size =0;

        }

        public void push(int x) {

            expandCapacity(size+1);
            stack[size-1]=x;
            size++;
            if (x<min){
                minSet.put(count,x);
                count++;
            }


        }
        public void expandCapacity(int newsize){

            size = newsize ;
            stack = Arrays.copyOf(stack,size);

        }


        //删除顶部元素
        public void pop() {
            int num = stack[--size];
            if (num == minSet.get(count-1)){
                minSet.remove(count-1);
                count--;
            }


        }

        public int top() {

            if (size>0){
                int temp =stack[size-1];
                size--;
                return temp;

            }else {
                return 0;
            }

        }

        public int getMin() {

            if (count>0){
                return minSet.get(count-1);
            }else {
                return 0;
            }


        }
    }

    /**
     * 题解：用双端队列 当deque被用作栈时，元素在deque的head端push/pop
     * 最小栈与数据栈同入同出
     *
     */
    class MinStack1{
        Deque<Integer> xStack;
        Deque<Integer> minStack;

        public MinStack1() {
            xStack = new LinkedList<Integer>();
            minStack = new LinkedList<Integer>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int x) {
            xStack.push(x);
            minStack.push(Math.min(minStack.peek(), x));
        }

        public void pop() {
            xStack.pop();
            minStack.pop();
        }

        public int top() {
            return xStack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }


    }


}
